1. Field of Invention
The present invention relates to network devices, including switches, routers and bridges, which allow for data to be routed and moved in computing networks. More specifically, the present invention provides for a multilevel parser for conditional flow detection for assisting in the flow of data in a network device and a network device having such a parser.
2. Description of Related Art
In computer networks, each element of the network performs functions that allow for the network as a whole to perform the tasks required of the network. One such type of element used in computer networks is referred to, generally, as a switch. Switches, as they relate to computer networking and to Ethernet, are hardware-based devices that control the flow of data packets or cells based upon destination address information, which is available in each packet or cell. A properly designed and implemented switch should be capable of receiving a packet and switching the packet to an appropriate output port at what is referred to wirespeed or linespeed, which is the maximum speed capability of the particular network.
Basic Ethernet wirespeed is up to 10 megabits per second, and Fast Ethernet is up to 100 megabits per second. Another type of Ethernet is referred to as 10 gigabit Ethernet, and is capable of transmitting data over a network at a rate of up to 10,000 megabits per second. As speed has increased, design constraints and design requirements have become more and more complex with respect to following appropriate design and protocol rules and providing a low cost, commercially viable solution.
A particular function that these network devices often perform is filtering the data that pass through the network devices. Such filtering of packets can be either static or dynamic and can examine a packet header to determine attributes of the packet, such as its source or destination, or examine other portions of the packet. Some network devices, in particular, have fast filtering processors that are independent of any central processing unit connected to the network device. Because of the independence of such a fast filtering processor, linespeed processing is more easily achieved and the functions of the processor can be tailored to the filtering functions required than could a central processing unit.
Many such filtering systems are similar to the filtering processes described in U.S. Pat. No. 6,335,935, which is hereby incorporated by reference, that provide filtering results. Additionally, these systems are often implemented using large, fixed size masks that are applied to portions of the packets. The application of the masks allows for fields of the packet fields to be extracted and the processor determines if extracted fields match configured values so that a proper action can be implemented. Additionally, filtering may also include management of flows through the network device and allow for the specific handling of certain data based on fields within the packet. These fields contain data about the source, destination, protocol and other properties of the packet. Classification of flows of flows of incoming packets on an ingress port of a network device is critical to providing differentiated services to different types of traffic flows.
However, these fast filtering processors require that a significant portion of the network device be utilized in the filtering process. The filtering processes are generally not expandable, often take a great number of cycles to process and increase the latency periods for address resolution lookup (ARL) and ingress processes. Given that the number of masks that can be applied is generally limited, the number of functions that a fast filtering processor can perform is also limited.
As such, there is a need for an efficient filtering method and a scalable filtering mechanism for data passing through network devices. There is also a need for filtering mechanisms that are more flexible and allows filtering masks to be reserved for classification of packets, especially where the extracted fields need to be extracted independent of the values of those fields. Also, there is a need for a powerful, flexible method of extracting relatively small fields from a datagram, where the extraction of the next field is optionally based on the value of the previous field, is described.